package com.peng.kslc;

import java.util.Comparator;
import java.util.PriorityQueue;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * A23MergeKLinkNode
 *
 * @author lupeng
 * Created on 2022-07-24
 */
public class A23MergeKLinkNode {

    private static final Logger logger = LoggerFactory.getLogger(A23MergeKLinkNode.class);

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode sentry = new ListNode(-1);
        ListNode curr = sentry;
        PriorityQueue<ListNode> minQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode listNode : lists) {
            if (listNode != null) {
                minQueue.add(listNode);
            }
        }
        while (!minQueue.isEmpty()) {
            ListNode min = minQueue.poll();
            curr.next = new ListNode(min.val);
            curr = curr.next;
            if (min.next != null) {
                minQueue.add(min.next);
            }
        }
        return sentry.next;
    }


}
